package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//DNA序列中只有A、C、G、T
//找到所有出现大于等于两次的长度为10的子串
public class RepeatedDNASequences {

	public List<String> findRepeatedDnaSequences(String s) {
		if (s == null) {
			return new ArrayList<>();
		}
		//the repeated can't be list
		//I got the error when using the arraylist to store the results when in put is "AAAAAAAAAAAA"
		Set<String> seen = new HashSet<>(), repeated = new HashSet<>();
		int length = s.length();
		String temp = "";
		for (int i = 0; i + 9 < length; i++) {
			temp = s.substring(i, i + 10);
			// 如果add返回false，说明之前已经加进去过，则说明出现了两次
			if (!seen.add(temp)) {
				repeated.add(temp);
			}
		}
		return new ArrayList<>(repeated);
	}
	
	//位运算
//	The key point is that it is not doing hash, it is doing the exact coding of a 10-letter sequence into
//	a 4-bytes number, which is simply not possible for any generic string, but is possible for strings in 
//	this problem because they can have only 4 differfent characters.
//	In more detail:
	
	//由于不同的子串可能具有相同的hash值，所以我们不能直接使用hashCode函数
//	If two objects have same hash it means that they may or may not be equal (though two equal objects are 
//	required to have same hash). So hashing is not enough here (like calling just "AACCCCCGGG".hashCode() and 
//	storing it in the map), because there can be another (different) string with same hash and the program 
//	will output wrong result.
    
	//我们也不能存储在内存中，因为可能会超限
//	We also cannot store the 10-letter substrings themselves because they consume too much memory and 
//	the program will exceed memory limit.
	
//	So, instead of hashing or storing strings themselves the solution converts 10 letter string into 
//	4-bytes integer (which is much smaller than string in terms of consumed memory). 
//	This would not be possible if the string could contain all 26 letters of English alphabet for example. 
//	But it is possible for our case, because there can be only 'A', 'C', 'G' and 'T' letters.
//	So we have only 4 possible letters, and we can use as little bits as possible to store each character of 
//	our 10-letter string. We really need only 2 bits (bits, not bytes) for this. 
//	Specifically the solution uses the following coding:
//	
//	0 = 00 (bits in binary number system) = 'A'
//
//	1 = 01 (bits in binary number system) = 'C'
//
//	2 = 10 (bits in binary number system) = 'G'
//
//	3 = 11 (bits in binary number system) = 'T'
//
//	Note that since there 10 letters and each letter requires only 2 bits, we will need only 10 * 2= 20 
//	bits to code the string (which is less then size of integer in java (as well as in all othere 
//	popular languages), which is 4 bytes = 32 bits).
//	For example, this is how "AACCTCCGGT" string will be coded:
//	A A C C T C C G G T
//
//	00 00 01 01 11 01 01 10 10 11 = 00000101110101101011 (binary) = 23915 (decimal)
	public List<String> findRepeatedDnaSequences2(String s) {
	    Set<Integer> words = new HashSet<>();
	    Set<Integer> doubleWords = new HashSet<>();
	    List<String> res = new ArrayList<>();
	    char[] map = new char[26];

	    map['A' - 'A'] = 0;
	    map['C' - 'A'] = 1;
	    map['G' - 'A'] = 2;
	    map['T' - 'A'] = 3;

	    for(int i = 0; i < s.length() - 9; i++) {
	        int v = 0;
	        //判断这个序列中所有的数字组成的位
	        for(int j = i; j < i + 10; j++) {
	        	//左移两位
	            v <<= 2;
	            v |= map[s.charAt(j) - 'A'];
	        }
	        //此时v是代表序列的十进制的数
	        //words.add(v)为false说明出现了两次
	        //doubleWords.add(v)为true，说明之前没有把该结果放进去
	        //也就是上一种解法中的不能把set改为list的原因的判断
	        if(!words.add(v) && doubleWords.add(v)) {
	        	res.add(s.substring(i, i + 10));
	        }
	    }
	    return res;
	}
}
